﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace System.Collections.Generic
{

    public class RecursionVisitor<TItem> 
    {

        public Action<RecursionVisitor<TItem>, TItem> EnteringAction;

        public Action<RecursionVisitor<TItem>, TItem> LeavingAction;

        public RecursionVisitor(
            IEnumerable<TItem> rootObjects, 
            Func<TItem, IEnumerable<TItem>> childrenSelector,
            Action<RecursionVisitor<TItem>, TItem> enteringAction,
            Action<RecursionVisitor<TItem>, TItem> leavingAction)
        {

            ColStack = new Stack<IEnumerator<TItem>>();
            ChildrenSelector = childrenSelector;
            var et = rootObjects.GetEnumerator();
            ColStack.Push(et);
            EnteringAction = enteringAction;
            LeavingAction = leavingAction;
           
        }


        Func<TItem, IEnumerable<TItem>> ChildrenSelector;

        public Stack<IEnumerator<TItem>> ColStack;


        TItem Current
        {
            get { return ColStack.Peek().Current; }
        }



        #region IDisposable Members

        public void Dispose()
        {
            ColStack.ToList().ForEach(o => o.Dispose());
            ColStack.Clear();
            ChildrenSelector = null;
            EnteringAction = null;
            LeavingAction = null;
        }

        #endregion





        private bool Started = false;

        virtual public bool MoveNext()
        {

            if (ColStack.Count > 0)
            {

                var cur = ColStack.Peek();
                
                if (Started)  //已经开始
                {
                    //主动找下一个节点
                    var en = ChildrenSelector(cur.Current).GetEnumerator(); //先看有没有子节点

                    if (en.MoveNext()) //有子节点  
                    {
                        // 把这个层加入堆栈 访问第一个节点
                        ColStack.Push(en);
                        EnteringAction(this, Current);//运行进入新节点操作
                        return true;
                    }
                    else //没有子节点 
                    {
                       
                        LeavingAction(this, Current); //离开本节点操作;
                        //进入下一个同层节点
                         
                        while (ColStack.Count > 0)
                        {
                            en = ColStack.Peek();
                          
                            if (en.MoveNext()) //有同层节点
                            {

                                EnteringAction(this, Current);//运行访问时内容
                                return true;//本次访问这个节点；

                            }
                            else//没有同层节点
                            {
                               
                                ColStack.Pop().Dispose();// 取消本层堆栈  
                                if (ColStack.Count > 0) LeavingAction(this, Current); //离开本节点操作;
                            }

                        }
                  
                        return false; //完全没有子节点 也没有下一个节点  就无法继续了
                    }



                }
                else //第一次访问 直接返回
                {
                    Started = true;
                    var rval = cur.MoveNext();
                    if (rval) EnteringAction(this, Current);//运行进入新节点操作
                    return rval ;
                
                }

            }
            return false;
        }



        public void Reset()
        {
            if (ColStack.Count > 0)
            {
                var emt = ColStack.Last();
                ColStack.Where(o => !o.Equals(emt)).ToList().ForEach(s => s.Dispose());


                emt.Reset();
                ColStack.Clear();
                ColStack.Push(emt);
                Started = false;
            }


        }

        public void Start()
        {

            while (MoveNext()) { };
        }

    }



    public class RecursionEnumeratorDepthFirst<TItem> : System.Collections.Generic.IEnumerator<TItem>, System.Collections.IEnumerator, IEnumerator<IEnumerable<TItem>>
    {


        public RecursionEnumeratorDepthFirst(IEnumerable<TItem> rootObjects, Func<TItem, IEnumerable<TItem>> childrenSelector)
        {

            ColStack = new Stack<IEnumerator<TItem>>();
            ChildrenSelector = childrenSelector;
            var et = rootObjects.GetEnumerator();

            ColStack.Push(et);

        }


      protected   Func<TItem, IEnumerable<TItem>> ChildrenSelector;

      protected Stack<IEnumerator<TItem>> ColStack;

        #region IEnumerator<TItem> Members

        public TItem Current
        {
            get { return ColStack.Peek().Current; }
        }

        #endregion

        #region IDisposable Members

      virtual   public void Dispose()
        {
            ColStack.ToList().ForEach(o => o.Dispose());
            ColStack.Clear();
            ChildrenSelector = null;

        }

        #endregion

        #region IEnumerator Members

        object System.Collections.IEnumerator.Current
        {
            get { return Current; }
        }



        protected bool Started = false;

        virtual public bool MoveNext()
        {
            if (ColStack.Count > 0)
            {

                var cur = ColStack.Peek();

                if (Started)  //已经开始
                {
                    //主动找下一个节点
                    var en = ChildrenSelector(cur.Current).GetEnumerator(); //先看有没有子节点

                    if (en.MoveNext()) //有子节点  
                    {
                        // 把这个层加入堆栈 访问第一个节点
                        ColStack.Push(en);
                        return true;
                    }
                    else //没有子节点 
                    {
                        //进入下一个同层节点

                        while (ColStack.Count > 0)
                        {
                            en = ColStack.Peek();
                            if (en.MoveNext()) //有同层节点
                            {
                                return true;//本次访问这个节点；

                            }
                            else//没有同层节点
                            {
                                ColStack.Pop().Dispose();// 取消本层堆栈  
                            }

                        }
                        return false; //完全没有子节点 也没有下一个节点  就无法继续了
                    }



                }
                else //第一次访问 直接返回
                {
                    Started = true;
                    return cur.MoveNext();
                }

            }
            return false;
        }



        public void Reset()
        {
            if (ColStack.Count > 0)
            {
                var emt = ColStack.Last();
                ColStack.Where(o => !o.Equals(emt)).ToList().ForEach(s => s.Dispose());


                emt.Reset();
                ColStack.Clear();
                ColStack.Push(emt);
                Started = false;
            }


        }

        #endregion

        #region IEnumerator<Stack<TItem>> Members

        IEnumerable<TItem> IEnumerator<IEnumerable<TItem>>.Current
        {
            get { return ColStack.Select(o => o.Current).Reverse ().ToList (); }
        }

        #endregion
    }
    public class RecursionEnumeratorBreadthWithAncestors<TItem> :  System.Collections.IEnumerator, IEnumerator<IEnumerable <TItem>>
    {
        Func<TItem, IEnumerable<TItem>> ChildrenSelector;




        /// <summary>
        /// 任务。对于一个节点的1层子节点遍历 叫做一个任务
        /// </summary>
        struct TaskItem
        {
            /// <summary>
            /// 本次任务要遍历的所有子节点
            /// </summary>
            public IEnumerator<TItem> CurrentTasks;
            /// <summary>
            /// 本次任务要遍历的父亲节点。因为不涉及 Pop() 这里只用list就可以了
            /// </summary>
            public List<TItem> ParentList;


        }

        bool started = false;
        Queue<TaskItem> TaskQueue;
        IEnumerable<TItem> roots;
        public RecursionEnumeratorBreadthWithAncestors(IEnumerable<TItem> rootObjects, Func<TItem, IEnumerable<TItem>> childrenSelector)
        {
            ChildrenSelector = childrenSelector;
            TaskQueue = new Queue<TaskItem>();
            var ti = new TaskItem() { CurrentTasks = rootObjects.GetEnumerator(), ParentList = new List<TItem>() };
            TaskQueue.Enqueue(ti);
            roots = rootObjects;

        }
        IEnumerator<TItem> CurrentEnum
        {
            get
            {

                return TaskQueue.Peek().CurrentTasks;
            }
        }


        #region IEnumerator<TItem> Members

        public TItem Current
        {
            get { return TaskQueue.Peek().CurrentTasks.Current; }
        }

        #endregion

        #region IDisposable Members

        public void Dispose()
        {
            TaskQueue.ToList().ForEach(s => s.CurrentTasks.Dispose());
            TaskQueue = null;
            roots = null;
            ChildrenSelector = null;
        }

        #endregion

        #region IEnumerator Members

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            if (TaskQueue.Count > 0)
            {
                if (started)
                {
                    while (TaskQueue.Count>0)
                    { 
                        if (CurrentEnum.MoveNext())
                        {
                            GainChildrenTask();
                            return true;
                        }
                        else
                        {
                            var t=  TaskQueue.Dequeue();
                            t.CurrentTasks.Dispose();
                            t.ParentList = null;                         
                        
                        }
                    }
                    return false;
                }
                else
                {

                    started = true;
                    if (CurrentEnum.MoveNext())
                    {
                        GainChildrenTask();
                        return true;
                    }
                    return false;
                }

            }




            return false;
        }

        void GainChildrenTask()
        {

            var cur = Current;
            TaskItem ti = new TaskItem()
             {
                 CurrentTasks = ChildrenSelector(cur).GetEnumerator(),
                 ParentList = TaskQueue.Peek().ParentList.Concat (new TItem[] { cur }).ToList()
             };

            TaskQueue.Enqueue(ti);

        }

        public void Reset()
        {
            var rootsbak = roots;
            var bakSelector = ChildrenSelector;
            Dispose();
            started = false;
            ChildrenSelector = bakSelector;
            TaskQueue = new Queue<TaskItem>();
            var ti = new TaskItem() { CurrentTasks = rootsbak.GetEnumerator(), ParentList = new List<TItem>() };
            TaskQueue.Enqueue(ti);
        }

        #endregion

        #region IEnumerator<IEnumerable<TItem>> Members

        IEnumerable<TItem> IEnumerator<IEnumerable<TItem>>.Current
        {
            get 
            { 
                return TaskQueue.Peek().ParentList.Concat( new TItem[]{ Current }).ToList () ; 
           
            }
        }

        #endregion
    }
            public class RecursionEnumeratorBreadth<TItem> : System.Collections.Generic.IEnumerator<TItem>, System.Collections.IEnumerator
    {
        Func<TItem, IEnumerable<TItem>> ChildrenSelector;




        bool started = false;
        Queue<IEnumerator <TItem >> TaskQueue;
        IEnumerable<TItem> roots;
        public RecursionEnumeratorBreadth(IEnumerable<TItem> rootObjects, Func<TItem, IEnumerable<TItem>> childrenSelector  )
        {
            ChildrenSelector = childrenSelector;
            TaskQueue = new Queue<IEnumerator <TItem >>();
            var ti = rootObjects.GetEnumerator();
            TaskQueue.Enqueue(ti);
            roots = rootObjects;

        }
        IEnumerator<TItem> CurrentEnum
        {
            get
            {

                return TaskQueue.Peek();
            }
        }


        #region IEnumerator<TItem> Members

        public TItem Current
        {
            get { return TaskQueue.Peek().Current; }
        }

        #endregion

        #region IDisposable Members

        public void Dispose()
        {
            TaskQueue.ToList().ForEach(s => s.Dispose());
            TaskQueue = null;
            roots = null;
            ChildrenSelector = null;
        }

        #endregion

        #region IEnumerator Members

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            if (TaskQueue.Count > 0)
            {
                if (started)
                {
                    while (TaskQueue.Count>0)
                    { 
                        if (CurrentEnum.MoveNext())
                        {
                            GainChildrenTask();
                            return true;
                        }
                        else
                        {
                            var t=  TaskQueue.Dequeue();
                            t.Dispose();
                             
                        
                        }
                    }
                    return false;
                }
                else
                {

                    started = true;
                    if (CurrentEnum.MoveNext())
                    {
                        GainChildrenTask();
                        return true;
                    }
                    return false;
                }

            }




            return false;
        }

        void GainChildrenTask()
        {

            var cur = Current;
            var ti =  ChildrenSelector(cur).GetEnumerator();
             

            TaskQueue.Enqueue(ti);

        }

        public void Reset()
        {
            var rootsbak = roots;
            var bakSelector = ChildrenSelector;
            Dispose();
            started = false;
            ChildrenSelector = bakSelector;
            TaskQueue = new Queue<IEnumerator<TItem>>();
            var ti = rootsbak.GetEnumerator();
            TaskQueue.Enqueue(ti);
        }

        #endregion


    }






    public static class RecursionExtender
    {
        public enum RecursionType
        { 
            DeepFirst=0,
            Breadth=1
        
        }

        static public IEnumerable <T> GetRecursionEnumerable<T>(this T SingleRoot, Func<T, IEnumerable<T>> childrenSelector , RecursionType type)
        {
            

            switch (type)
            { 
                case RecursionType.DeepFirst :
                    return new EmptyEnumerable <T>(new RecursionEnumeratorDepthFirst<T>(new T[] { SingleRoot }, childrenSelector));
                case RecursionType.Breadth :
                    return new EmptyEnumerable<T>(new RecursionEnumeratorBreadth <T>(new T[] { SingleRoot }, childrenSelector));
            }

            return null;
        }


        static public IEnumerable <IEnumerable <T> >GetRecursionEnumerableWithAncestors<T>(this T SingleRoot, Func<T, IEnumerable<T>> childrenSelector , RecursionType type)
        {
            

            switch (type)
            { 
                case RecursionType.DeepFirst :
                    return new EmptyEnumerable <IEnumerable<T>>(new RecursionEnumeratorDepthFirst<T>(new T[] { SingleRoot }, childrenSelector));
                case RecursionType.Breadth :
                    return new EmptyEnumerable<IEnumerable<T>>(new RecursionEnumeratorBreadthWithAncestors <T>(new T[] { SingleRoot }, childrenSelector));
            }

            return null;
        }



        static public IEnumerable<T> GetRecursionEnumerableAsRootCollection<T>(this IEnumerable<T> Roots, Func<T, IEnumerable<T>> childrenSelector, RecursionType type)
        {
            switch (type)
            {
                case RecursionType.DeepFirst:
                    return new EmptyEnumerable<T>(new RecursionEnumeratorDepthFirst<T>(Roots, childrenSelector));
                case RecursionType.Breadth:
                    return new EmptyEnumerable<T>(new RecursionEnumeratorBreadth<T>(Roots, childrenSelector));
            }

            return null;
        }


        static public IEnumerable<IEnumerable<T>> GetRecursionEnumerableAsRootCollectionWithAncestors<T>(this IEnumerable<T> Roots, Func<T, IEnumerable<T>> childrenSelector, RecursionType type)
        {


            switch (type)
            {
                case RecursionType.DeepFirst:
                    return new EmptyEnumerable<IEnumerable<T>>(new RecursionEnumeratorDepthFirst<T>(Roots, childrenSelector));
                case RecursionType.Breadth:
                    return new EmptyEnumerable<IEnumerable<T>>(new RecursionEnumeratorBreadthWithAncestors<T>(Roots, childrenSelector));
            }

            return null;
        }




    }


}
